import collections


# 暴力筛选
# class Solution(object):
#     def countPrimes(self, n):
#         """
#         :type n: int
#         :rtype: int
#         """
#         if n <= 2:
#             return 0
#
#         zhishu = collections.deque([2])
#         for k in range(3, n):
#             flag = True
#             for item in zhishu:
#                 if k % item == 0:
#                     flag = False
#                     break
#                 if item > k ** (1/2):
#                     break
#             if flag:
#                 zhishu.append(k)
#         return len(zhishu)

class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        isPrime = [1] * n
        for i in range(n):
            if i <= 1:
                isPrime[i] = 0
            else:
                if isPrime[i] == 1:
                    k = i
                    while k * i < n:
                        isPrime[k * i] = 0
                        k += 1
        return sum(isPrime)



data = Solution()
n = 5000000
print(data.countPrimes(n))
